// 最小覆盖子串

#include <string>
using namespace std;

class Solution
{
public:
    string minWindow(string s, string t)
    {
        int hash1[128] = { 0 };
        int kinds = 0; // 统计字符种类
        for(auto ch : t)
            if(hash1[ch]++ == 0) kinds++;

        int hash2[128] = { 0 };
        int begin = -1, minlen = INT_MAX;
        for(int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            hash2[in]++; // 进窗口
            if(hash2[in] == hash1[in]) count++; // 维护 count
            while(count == kinds)
            {
                if(right - left + 1 < minlen)
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if(hash2[out] == hash1[out]) count--; // 维护 count
                hash2[out]--; // 出窗口
            }
        }
        return begin == -1 ? "" : s.substr(begin, minlen);
    }
};